package com.sanyue.dataStructure;

import org.junit.Test;

import java.util.ArrayList;

/**
 * @author sanyue
 * @version 1.0
 * @description: TODO-算法-Algorithm（算法：同一问题的不同解决方法）
 * @date 2022/1/25 上午10:47
 */
public class Algorithm {
    static int[] arr = {1, 3, 5, 6, 2, 4, 8, 9, 7, 0, 1, 2, 3, 4};

    //插入排序
    @Test
    public void testInsertionSort() {
        int[] ans = InsertionSort(arr);
        System.out.println("InsertionSort:");
        print(ans);
    }

    //插入排序
    //核心思想 把第二个开始后到每个数插入到左侧有序数中去
    public int[] InsertionSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            for (int j = i; j > 0; j--) {
                if (arr[j] < arr[j - 1]) {
                    swap(arr, j, j - 1);
                }
            }
        }
        return arr;
    }


    //冒泡排序
    @Test
    public void testbubbleSort() {
        int[] ans = bubbleSort(arr);
        System.out.println("bubbleSort:");
        print(ans);
    }

    //冒泡排序 平均时间O(n^2) 空间O(1)
    //核心思想：每次循环，将最大/最小值向后移动，一轮循环一个最大/小值移到目标位置
    public int[] bubbleSort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[i] > arr[j]) swap(arr, i, j);
            }
        }
        return arr;
    }

    //选择排序
    @Test
    public void testselectionSortlve() {
        int[] ans = selectionSort(arr);
        System.out.println("selectionSortlve:");
        print(ans);
    }

    //选择排序 平均时间O(n^2) 空间O(1)
    //核心思想：每次从（i,n）的范围内选出最小值放在最前面，i++
    public int[] selectionSort(int[] arr) {

        for (int i = 0; i < arr.length - 1; i++) {
            int minindex = i;

            for (int j = i + 1; j < arr.length; j++) {
                minindex = arr[minindex] >= arr[j] ? j : minindex;
            }

            swap(arr, i, minindex);
        }

        return arr;
    }

    //通用方法提取

    //交换
    void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    //打印
    void print(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }

}
